GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Null-Zug-Suche</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Null-Zug-Suche</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Mit <b>Null-Zug-Suche</b> (<i>nullmove pruning</i>) bezeichnet man eine <i>Forward-<a href="Pruning" title="Pruning">Pruningtechnik</a></i> in Spielbaum<a href="Suchverfahren#Suche_in_Bäumen" title="Suchverfahren">suchverfahren</a> für Zwei-Personen-<a href="Nullsummenspiel" title="Nullsummenspiel">Nullsummenspielen</a> mit <a href="Spiel_mit_perfekter_Information" title="Spiel mit perfekter Information">perfekter Information</a>.

</p><p>Speziell in <a href="Schachprogramm" title="Schachprogramm">Schachprogrammen</a> hat sich das <i>Nullmove Pruning</i> bewährt. Diese Technik wird benötigt, um die Ermittlung der Spielstärke möglicher Züge bzw. Spielverläufe zu beschleunigen, indem Züge, welche durch unten beschriebenes Verfahren als zu schwach ermittelt werden, von einer weiteren Berechnung ausgeschlossen werden.

</p><p>Ausgehend von der Annahme, dass das Zugrecht einen Vorteil darstellt, wird beim <i>Nullmove Pruning</i> in der Baumsuche (Weiterverfolgung von Stellungsmöglichkeiten, die sich aus einem Zug ergeben) einer Seite ermöglicht, zwei Züge auszuführen. Ist der dadurch erzielte Vorteil nicht groß genug, so war wahrscheinlich schon der erste der beiden Züge minderwertig, und der daraus resultierende Ast des Spielbaums (sämtliche mögliche Spielverläufe, die sich aus der aktuellen Stellung ergeben können) braucht nicht weiter untersucht zu werden, er wird abgeschnitten. Hierdurch können minderwertige Varianten gut und schnell erkannt werden und die zur Verfügung stehende Zeit für die Analyse wichtigerer Varianten genutzt werden.

</p><p>Um insgesamt den Suchaufwand zu reduzieren, muss die Baumsuche, mit der der Null-Zug bewertet wird, mit geringerer Suchtiefe durchgeführt werden, als die Suche zur Bewertung normaler Züge. Eine Reduktion der Suchtiefe um zwei Halbzüge hat sich als vorteilhaft herausgestellt. Manche Programme arbeiten auch mit einer Reduktion um drei Halbzüge, was ein stärkeres Pruning bewirkt, aber taktisch etwas anfälliger ist, da auch vielversprechende Züge mit aussortiert werden können.

</p><p>Das normale <i>Nullmove Pruning</i> versagt in Zugzwangstellungen, da hier die <a href="Pr%C3%A4misse" title="Prämisse">Prämisse</a> nicht erfüllt wird. Es kann ein taktisch nachteiliger Zug durch den <a href="Zugzwang" title="Zugzwang">Zugzwang</a> erforderlich sein.

Da Zugzwangstellungen beim Schach relativ selten vorkommen (am ehesten in bestimmten Endspielsituationen), ist die Fehlerhäufigkeit eher gering. Einige Schachprogrammierer schalten das Nullmove Pruning im Endspiel auch einfach ganz ab, da gerade am Ende nur noch wenige Zweige des Baumes übrig sind und diese eher Zugzwangsstellungen sein können.

</p><p>Bei Spielen wie <a href="Dame_(Spiel)" title="Dame (Spiel)">Dame</a> (engl. <i>checkers</i>) gehören Zugzwangstellungen zum Normalfall, weshalb bei solchen Spielen diese Technik nicht angewandt wird.

</p><p>Eine verbesserte Technik nennt sich <i>Verified Nullmove Pruning</i><sup id="cite_ref-vnp_1-0" class="reference"><a href="#cite_note-vnp-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> und umgeht die Probleme in Zugzwangstellungen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Quellen">Quellen</h2></div>

<li id="cite_note-vnp-1"><span class="mw-cite-backlink"><a href="#cite_ref-vnp_1-0">↑</a></span> <span class="reference-text">Omid David Tabibi and Nathan S. Netanyahu (2002), <a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7164">Verified Null-Move Pruning</a></span>

</li>

</ol>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.mustrum.de/chrilly/nullmove.pdf">Die Kunst des Nichtstuns</a> – <a href="Christian_Donninger" title="Christian Donninger">Christian Donninger</a> über den Null-Move-Algorithmus (PDF; 1,24 MB)</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2019-08-02" href="https://de.wikipedia.org/wiki/?title=Null-Zug-Suche&oldid=190971563">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>